package leetcode_day._2021._202109._1120;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/9/14 9:56
 * 通过删除字母匹配到字典里最长单词
 * 算法：双指针  枚举  排序
 * 先将 dictionary 排序，找到第一个符合的就返回结果
 */
public class _14_524 {
    public static void main(String[] args) {
        String s = "abpcplea";
        final List<String> dictionary = Arrays.asList("ale", "apple", "monkey", "plea");
        System.out.println(new _14_524().findLongestWord(s, dictionary));
    }

    public String findLongestWord(String s, List<String> dictionary) {
        Collections.sort(dictionary, (a, b) -> {
            if (a.length() != b.length()) return b.length() - a.length();
            else return a.compareToIgnoreCase(b);
        });
        int len = s.length();
        for (String dic : dictionary) {
            int p = 0;
            for (int i = 0; i < len; i++) {
                if (s.charAt(i) == dic.charAt(p)) {
                    if (++p == dic.length()) break;
                }
            }
            if (p == dic.length()) return dic;
        }
        return "";
    }

}
